<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>无标题文档</title>
</head>

<body>
	请输入数据:<input id="data"/><br/><br/>
    请输入查找的key:<input id="key"/><br/><br/>
    点击查找:<input type="button" id="find" value="查找"/><br/><br/>
    
    key所在的下标:<span id="result"></span>
    <script>
    	window.onload = function(){
		
			var find_key = document.getElementById("find");
			find_key.onclick=function(){
				 var data =  document.getElementById("data").value;
				 var array = data.split(",");
				 
				 var key_value = document.getElementById("key").value;
				 
				 if(array instanceof Array && array != null && array.length > 0){
					  if(checkOutArray(array) == true){
						  var index = binarySearch(array,key_value);
						  if(index != -1){
						  	 document.getElementById("result").innerHTML = index;
						  }else{
						     document.getElementById("result").innerHTML = "序列中无要查找的key值!!!!";
						  }
						 
					  }else{
						     document.getElementById("result").innerHTML = "输入非升序序列!!!!";
						 }
					  
				}else{
					document.getElementById("result").innerHTML = "数据输入有误!!!!";
				}
				
			}
			
			
			/*
			*此函数通过二分法用来查找指定的key值
			*输入：输入一个待查找的数组和待查找的Key值
			*返回:  1.如果找到，返回key值所对应的下标
			*      2.如果没有找到，返回-1.
			*/
			function binarySearch(array,key){
				var low = 0;
				var high = array.length-1;
				while(low <= high){

					var mid = (low + high)/2;
					if(array[mid] < key){
						low = mid + 1;
					}else if(array[mid] > key){
						high = mid - 1;
					}else{
						console.log(low+":"+high+":"+array[mid]);
						return mid;
					}
				}
				
				if(low > high) 
					return -1;
			}
			
			/*
			*此函数用来检测输入的数组是否是升序有序的
			*输入：输入一个待判断的数组
			*返回:  1.如果有序，则返回true
			*      2.如果无序，则返回false
			*/
			function checkOutArray(array){
				var i ;
				var flag = true;
				for(i = 1;i < array.length;i++){
					if(array[i] < array[i-1]) {
						flag = false;
						break;
					}
				}
				return flag;
			}
			
		}
    
    </script>

</body>
</html>
